use std::fmt::{Display,Debug};
use std::default::Default;
use std::io::Write;
use super::blocks::mem::Bar;
use super::umutex::ScopedLock;

pub trait HeapIndex {
    type Output:Copy+Display+Debug;
    fn hindex<'a>(&'a self, idx: usize) -> &'a Self::Output;
    fn hindex_mut<'a>(&'a mut self, idx: usize) -> &'a mut Self::Output;
    fn less(&self,a:usize,b:usize) -> bool;
    fn swap(&mut self,a:usize,b:usize);
}

pub trait HeapSized {
    const BUF_LEN:usize;
    const HEAD_START:usize;
    type BufArray:Sized+HeapIndex+Default;
    type Item:Display;
}

#[repr(C)]
#[derive(Default)]
pub struct Heap<L> where L:HeapSized {
    pub bar:Bar,
    pub buf:L::BufArray,
}

impl<L:HeapSized> Heap<L> {
    fn down(&mut self,index:usize) {
        if(self.bar.pos > index) {
            let left = index*2+1;
            let right = index*2+2;
            let mut small = index;
            if right < self.bar.pos && self.buf.less(right,small) {
                small = right;
            }
            if left < self.bar.pos && self.buf.less(left,small) {
                small = left;
            }  
            if small != index {
                self.buf.swap(index,small); 
                self.down(small);
            }
        }
    }
    
	fn up(&mut self, index:usize) {
		if index != 0 {
            let pup = (index-1)/2;
            if self.buf.less(index,pup) {
                self.buf.swap(pup,index);
                self.up(pup);
            }
        }
	}
    pub fn HeapSize() -> usize { L::BUF_LEN }
    fn insert_internal(&mut self,a:<<L as HeapSized>::BufArray as HeapIndex>::Output) -> 
    Option<<<L as HeapSized>::BufArray as HeapIndex>::Output> {
		// let _l = ScopedLock::new(&mut self.bar.bar_mutex);
		self.bar.bar_mutex.lock();
        if self.bar.pos < L::BUF_LEN {
            let end = self.bar.pos;
			*self.buf.hindex_mut(end) = a;
			self.bar.pos = end+1;
			self.up(end);
            self.bar.bar_mutex.unlock();
			Some(a)
		} else {
            self.bar.bar_mutex.unlock();
            None
        }
	}
    pub fn insert(&mut self,a:<<L as HeapSized>::BufArray as HeapIndex>::Output) -> 
    Option<<<L as HeapSized>::BufArray as HeapIndex>::Output> {
        if self.bar.pos < L::BUF_LEN-1 {
			self.insert_internal(a)
		} else {
            None
        }
	}
    pub fn pop(&mut self) -> Option<<<L as HeapSized>::BufArray as HeapIndex>::Output> {
		// let _l = ScopedLock::new(&mut self.bar.bar_mutex);
        self.bar.bar_mutex.lock();
        let pos = self.bar.pos;
		if pos > 0 {
            let r = *self.buf.hindex(0usize);
            self.buf.swap(0,pos-1);
            self.bar.pos = pos-1;
            self.down(0usize);
            self.bar.bar_mutex.unlock();
            Some(r)
        } else {
            self.bar.bar_mutex.unlock();
            None
        }
    }
    pub fn empty(&mut self) {
        self.bar.pos = 0usize;
    }
    pub fn dump(&self,f:&mut Write) {
        let p = self.bar.pos;
        let mut m = 1usize;
        let mut s = 0usize;
        writeln!(f,"pos {}",p);
        for l in 0usize .. p {
            write!(f,"{:?} ",self.buf.hindex(l));
            s += 1;
            if s==m {
                writeln!(f,"");
                s = 0usize;
                m *= 2usize;
            }
        }
        writeln!(f,"");
    }
}





